/*
 * @lc app=leetcode.cn id=1542 lang=cpp
 *
 * [1542] 找出最长的超赞子字符串
 *
 * https://leetcode.cn/problems/find-longest-awesome-substring/description/
 *
 * algorithms
 * Hard (44.99%)
 * Likes:    91
 * Dislikes: 0
 * Total Accepted:    6.3K
 * Total Submissions: 13.1K
 * Testcase Example:  '"3242415"'
 *
 * 给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
 *
 * 「超赞子字符串」需满足满足下述两个条件：
 *
 *
 * 该字符串是 s 的一个非空子字符串
 * 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
 *
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "3242415"
 * 输出：5
 * 解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
 *
 *
 * 示例 2：
 *
 * 输入：s = "12345678"
 * 输出：1
 *
 *
 * 示例 3：
 *
 * 输入：s = "213123"
 * 输出：6
 * 解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
 *
 *
 * 示例 4：
 *
 * 输入：s = "00"
 * 输出：2
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= s.length <= 10^5
 * s 仅由数字组成
 *
 *
 */
#include <bits/stdc++.h>

#include "help_struct.h"
using namespace std;
// @lc code=start
class Solution {
public:
    int longestAwesome(string s) {
        unordered_map<int, int> map;
        int n = s.size(), mask = 0, ans = 1;
        map[mask] = -1;
        for (int i = 0; i < n; i++) {
            mask ^= (1 << (s[i] - '0'));
            if (map.count(mask) == 0)
                map[mask] = i;
            else
                ans = max(ans, i - map[mask]);
            
            for (int j = 0; j < 10; j++) {
                int need = mask ^ (1 << j);
                if (map.count(need)) {
                    ans = max(ans, i - map[need]);
                }
            }
        }

        return ans;
    }
};
// @lc code=end

int main() {
    cout << Solution().longestAwesome("3242415");   // 5
    cout << Solution().longestAwesome("12345678");  // 1
    cout << Solution().longestAwesome("213123");    // 6
    cout << Solution().longestAwesome("00");        // 2
    return 0;
}